package com.beney.ds.sorting;

import java.util.Arrays;

public class RadixSort {
    private static final int DEFAULT_RADIX = 10;

    private RadixSort() {
    }

    public static void sort(int[] a) {
        sort(a, DEFAULT_RADIX);
    }

    public static void sort(int[] a, int radix) {
        int[] b = new int[a.length];
        System.arraycopy(a, 0, b, 0, a.length);
        sort(a, b, radix);
    }

    private static void sort(int[] a, int[] b, int radix) {
        int len = a.length, j;
        int[] cnt = new int[radix];
        for (int i = 0, rtok = 1;
             i < radix;
             ++i, rtok *= radix) {  // 遍历每一位
            Arrays.fill(cnt, 0);
            for (j = 0; j < len; ++j) cnt[(a[j] / rtok) % radix] += 1; // 统计每位出现次数
            for (j = 1; j < radix; ++j) cnt[j] += cnt[j - 1];   // cnt前缀和=每一位在结果中的最后位置
            for (j = len - 1; j >= 0; --j)
                b[ --cnt[(a[j] / rtok) % radix] ] = a[j];
            for (j = 0; j < len; ++j)
                a[j] = b[j];  // 更新完的结果拷贝回a
        }
    }
}
